UR 做题记录
$UR$ $6$
智商锁
点数不超过 $100$ 的无向图，满足生成树个数模意义下为 $k$
看那个数据范围！$k$ 非常诡异！ 考虑构造一些图然后拿链把它们串起来使得方案数为它们各自的相乘，恰好为 $k$（很自然的想法）
……然后怎么做啊（虚弱）
膜题解
绝了！随机化 + 概率分析 + 数感！全是我不会的东西！！！
考虑生成 $1000$ 个点数为 $12$ 的图，从中任取 $4$ 个图串起来，矩阵树算出图的生成树个数
即 $f(G1)f(G2)f(G3)f(G4) \equiv k \pmod{998244353}$，可以预处理两两乘积，丢到 map 里
由于 $n^{n - 2} = 12^{10} > 998244353$，取模后可以看作 $[0, 998244353)$ 的随机数
相当于我们有 $1000^{4} = 10^{12}$ 个随机数
$10^{12}$ 个随机数完全覆盖 $[0, 998244353)$ 的概率是多少？我们可以近似的看作 $10^9$ 个数需要被覆盖
实际上是 $1 - (1 - \frac{1}{10^9})^{10^{12}} \approx 1 - e^{-10^3}$，非常接近 $1$
后记：爆了 $17$ 发 OJ，一定是上天被感动了才放我过了 Extra Test【感动】一模一样的代码一遍 $70$ 一遍 $100$ 吐了呀
懒癌
以前写的，又不会做了 = = 神仙题！！！
根据完全图提示，开枪策略是假设我的狗没病，取 $time = \max\limits_{S \in 我看不到的集合}( S 开枪时间 )$，那么如果 $time$ 以前都没有开枪我就要在 $time + 1$ 开枪。
建出补图（即看不到关系组成的图）如果有病狗在环里，逻辑链条就永远不可能停止。否则缩点，DAG。
仔细思考上面 dp，可以构造解法：初始染黑一些点表示病狗，白的表示健康，每次选一个黑点染白，并将它的相邻点集的一个子集染黑，最终把整个图染白。这样的开枪时间为一度染黑过的点数，即所有黑点能到达的点数。这个过程和 dp 过程很类似 （根本就不是人类能想到的吧！） 证明可以考虑归纳。
显然最优策略是每次染全部相邻点，这样才能最大化到达的点数。
为什么这就是最小开枪时间？（一旦有人开枪就停止）因为这是 DAG，一定有黑点处在不可被其他黑点到达的位置，这些黑点就是开枪的点，即从他们出发得到最小开枪时间（这个只能从逻辑上理解了……）第二问就很好回答了，每个点 $x$ 对答案的贡献就是 $2^{n - 可以到达 x 的点数}$
第一问也是考虑每个点被到达，对答案的贡献。如果 $x$ 能被 $i$ 个点到达，方案数就是 $(2^i - 1) * 2^{n - i}$。
$UR$ $7$
水题走四方
不妨看作只有分身在瞬移。那么本体走的是一条通到叶子的链。
记录 $sd[x]$ 表示 $x$ 子树的叶子深度和，$num[x]$ 表示 $x$ 子树的叶子个数。路径上有若干个关键点，是本体可能会停的点。
考虑 dp。设上个关键点为 $u$，当前关键点为 $v$。
若分身走的最后一个叶子的深度 $< dep[v]$，那么到达叶子后就可以瞬移并和本体一起走到 $v$。这样 $v$ 显然不是关键点，因为瞬移回来的那个才是。
设 $md[u, v]$ 表示 $u$ 到 $v$ 路径上（不包括 $v$）所有延伸子树的叶子深度 max。
这样对于 $v$ 就只要考虑 $md[u, v] \geq dep[v]$ 的 $u$ 作为上一个关键点，并且 $md[u, v]$ 对应的叶子出现在 $u$ 这个节点的延伸子树里。
若 $v$ 有俩祖先都可以作为关键点，那必然是两者一起成为关键点最不劣。因此要求最深的 $u$ 满足 $md[u, v] \geq dep[v]$，设为 $fr[v]$
考虑长剖，从下往上做，维护还未找到 $fr$ 的点的链表，每次合并俩子树的链表，长儿子所在的子树一定不为空，而另一子树一定空，因此复杂度 $O(n)$。
$UR$ $14$
最强跳蚤
我们只关注每种质因子能否抵消干净，这个用 bitset 大材小用了，只要给每个质因子分配一个 $[0, 2^64]$ 的权值即可。不出错的概率是 $(1 - \frac{1}{2^{64}})^{\binom{100000}{2}} \approx 0.99999999973$
惨遭 Extra Test 卡常，一通 registeR$ int、inline 后艹过去了……
人类补完计划
以前写的。
要求的就是所有基环树中 $2$ 的「非叶节点的个数」次方。
给这个 $2$ 赋予实际意义：基环树上点黑白染色的方案数，其中叶子只能染白。
设 $h(s)$ 表示点集 $s$ 构成的基环树个数。
枚举染成了黑色的不合法点集合 $t$，容斥：
$ans_s = \sum_{t \subset s} (-1)^{|t|} 2^{|s - t|} h[s - t] [t 向 s - t 中的点连边的方案数]$
考虑 $h(s)$ 怎么求？仅有一个环很好求，叶子数 $\geq 1$ 的方案数就状压 + 容斥求。
思考熊
题意：插入、删除点，询问点 $x$ 到一个区间的点的最大距离，要求强制在线。
权值为正：
- 线段树维护点集直径就行了。
权值可以为负：
- 就只能建虚树处理每个点集中的节点到子树内和子树外最大距离。虚树合并只能重建。
没有删除：
- 二进制分组，合并就两遍 dfs 合并虚树。
- 因为要查询区间，所以合并时要新建点指向被合并的区间，查询就像线段树那样，空间是 $O(nlogn)$。
带删除：
- 类 $Unknown 做法！就是，这一层的下个区间插满了，就合并当前区间。
- 删除时，给当前块打标记表示信息错误，$O(1)$。
- 插入时，当前块打标记，如果插满了就看同层前驱块有没有标记，有就重建前驱块。第 $i$ 层重建一个块的复杂度是 $O(i 2^i)$，均摊分析第 $i$ 层总复杂度 $O(ni)$，求和是 $O(nlog^2n)$。
- 查询时，碰到标记区间就要递归下去。一个块最多查询 $log$ 次所以 $O(log^2n)$。
惨遭 Extra Test 卡空间，竟严苛到个位，大无语事件。
$UR$ $17$
$T1$
题目看错了！是前缀 and！
显然最终一定是链，挂在链的最下方肯定比挂在之前的某个节点下优。
$f_S = \min( f_{S \& a_i} + (S \& a_i) )$
然而每次减少正整数个位，而且一个 $a_i$ 不会被 $\&$ 两次，想到枚举子集，预处理哪些子集可以被减掉。虽然也很爆炸但总比 $O(nA)$ 好。
要剪枝！就nm滑稽！
$T2$
二分。怎么判定？
幸好这是直的，所以一个人的轨迹固定，另一个人就是单调的。设 $(x, y)$ 表示一个人在点 $x$，另一个在点 $y$ 的状态，$(x1, y1)$ 和 $(x2, y2)$ 可达当且仅当两人的距离都 $\leq lim$。$f_{x, y}$ 表示状态 $x$ 是否合法，从 $(stx, sty)$ 开始跑 bfs 就行了？
但是有可能一个人为了配合另一个人而同时移动诶！GG
冷静思考。准确来说应该是如果两个状态中两人所在的边都相同。你不会让 $f_{x, y}$ 表示一个人在边 $x$，另一个在边 $y$ 吧？很难转移的。
$f_{x, y}$ 表示一个人在点 $x$，另一个在边 $y$ 上距离点 $x$ 最近的位置。讨论是谁在配合谁，转移分两种：
- 第一个人从 $x$ 走到相邻边，为了配合第二个人走到 $y$ 的某个端点。
- 第二个人仍旧在 $y$ 上走，为了配合第一个人从 $x$ 走到相邻点。
$T3$
完全不会啦……
考虑如何求 $Pr[\lambda \leq x]$。设 $g(s, x, t)$ 表示点集 $s$ 点权最大值 $\leq x$，$\max(点权最大值，边权最大值) \leq t$ 的概率。
- 若点权都 $\leq \frac{t}{2}$ 则概率就是 $(\frac{t}{2})^{|s|}$
- 否则最大点权 $> \frac{t}{2}$，考虑扣掉最大点权的点和与它直接相连的点集，不会和剩下的点矛盾。（为什么？）
$s’$ 表示从 $s$ 中扣掉「最大点权的点和与它直接相连的点集」后的集合。
$g(s, x, t)$ 其实是个关于 $x$ 和 $t$ 的二元生成函数。那怎么求啊？？
我们发现每一项 $x^i t^j$ 都满足 $i + j = |s|$（积分后项数加一），那么把 $x$ 当作主变量就好啦（就是把 $t^k$ 看作 $x^{n - k}$）。
上面那个柿子，$\int$ 有下界，怎么办？$t$ 被视为常数啦，所以 $y \leq \frac{t}{2}$ 的贡献就从常数项里减掉。
最终答案里 $x$ 只要不超过 $t$ 即可，因此：
这时把 $t$ 当成主变量，那么把形式幂级数 reverse 一下就可以了~
xml 弱弱问道：怎么算微积分……
$\mathscr{Naive}$！求导 + 积分啊
实现细节：不同连通块分别做然后乘起来，可以大大减小状态数。
$UR$ $19$
清扫银河
以前做的，题解也是以前写的，现在看看好简单嘛！ε-(´∀｀; )
若有解则必然可以在 $m + 1$ 次操作里出解。
- 证明：首先要知道一个性质：无向图的任何环都可以由若干个非树边覆盖的环异或得到。也就是说有用的操作一只有 $m - n + 1$ 个。而操作二等价于每次选一个点，将与这个点相邻的边全部反转，也就是说有用的操作二有 $n$ 个。
总共操作数为 $m + 1$ 个，解异或方程组，必然可以在 $m + 1$ 次操作里出解，况且多个操作二还可以合成一个呢。
直接做 $O(m^3 / 32)$，考虑优化。
将所有 $1$ 边形成的图称为目标子图。根据欧拉回路的知识，若目标子图中每个节点的度数都是偶数，则必然可以通过不超过 $m - n + 1$ 次操作一将边权都变成 $0$。
因此只要考虑，仅用操作二能否让目标子图中每个节点度数变成偶数。这样是 $O(n^3 / 32)$ 的。
异或什么的想想方程组啊，，，虽然暴力，但到底是个切入口。不过后续就需要找性质了。
正式做题时，逆推回去比较好：环上点的度数都是偶数…所以blabla
通用测评号
读清题啊，添加燃料是无限的，加加加直到全员达到 $b$，所以转化题意为：到 $a$ 的舱也可以选，求达到 $a$ 舱个数的期望
又发现每个舱都是相同的，我们只要考虑 $1$ 舱在全员达到 $b$ 前达到 $a$ 的概率然后乘 $n$。
和猎人杀有点像，现在我们只关注 $1$ 舱是否到 $a$，所有非 $1$ 舱是否全到 $b$，有用的操作序列长度仅为 $b(n - 1) + a$，给已经到 $b$ 的非 $1$ 舱 $+1$ 的操作可以忽视。
相当于现在要求 $b(n - 1) + a$ 项中最后一项给 $1$ 舱的概率（忽视操作乘给概率的贡献为 $1$）
设 $n - 1$ 个非 $1$ 舱到 $b$ 的时间分别为 $t_1, \cdots, t_{n - 1}$
概率 = 方案数 / 总数：
根据上柿 dp, dp 当然要一步步来啦，每步都乘分母那玩意，换阶段了乘分子那玩意，$dp_{i, j}$ 表示到 $i$ 时间，有 $j$ 种非 $1$ 舱到 $b$ 了，$O(n^3)$。
生成函数也能做到 $O(n^3)$，口胡一波？
设 $F(x) = \sum\limits_{i = 0}^{b - 1} \frac{x^i}{i!}$，
答案生成函数 $= \frac{x^{a - 1}}{(a - 1)!} \sum\limits_{i = 1}^{n - 1} \binom{n - 1}{i} F^i(x) ( e^x - F(x) )^{n - 1 - i}$
我们要求 $F^i(x)$。
$F’(x) = F(x) - \frac{x^{b - 1}}{(b - 1)!}$（正常求导……）
设 $G_k(x) = F^k(x)$，
$G_k’(x) = kF^{k - 1}(x) F’(x)$（归纳证明），$= kG_{k}(x) - k \frac{x^{b - 1}}{(b - 1)!} F^{k - 1}(x)$，积分，就可以递推啦。预处理 $e^x - F(x)$。
前进四
画出图来嘛。每个操作在时间线段树上影响的都是一段区间。
由于是后缀 $\min$，考虑从后往前维护时间线段树，支持区间取 $\min$（sgt beats 即可）
应对询问，相当于最后单点询问时间线段树上某个位置被取 $\min$ 的次数。想不到吧这个可以在 sgt beats 区间取 $\min$ 的时候一并维护！
具体来说，设 $mx’[x]$ 表示新的 $mx[x]$，修改最大值时打标记，如果 $mx’[x] < mx[ls]$ 或 $< mx[rs]$ 就下传。
什么这样不会出现 $x$ 节点的标记不对下传节点 $y$ 起效而多算的情况嘛？
不会的。我们分讨说明：
首先既然是累计了好多次标记一次性下传说明 $se[x]$ 没有改动。$mx[x] > mx’[x] > se[x]$。
- $se[x] \geq mx[y]$：$y$ 不可能是下传节点。
- $se[x] < mx[y]$：$mx[x] = mx[y]$!!!
（智障问题++）
$UR$ $20$
切了签到题，上分了 _QAQ_
跳蚤电话
方案合法的充要条件是新加点和任意已选点的 LCA 都已选，我们将其称为「和谐」。直接做不好搞，考虑 dp——类似分治思想，只要保证 $x$ 的每个子树都和谐，dp 的时候再维护一下就能让 $x$ 的子树和谐了。
怎么维护？具体来说有两种情况：
- 选 x 再任意排子树
- 选一个子树任意排，再选 x，剩下的子树任意排
这样就不会出现「选择不同子树的点，$x$ 作为它们的 LCA 没有被选」的情况了。
机器蚤分组
最小链覆盖 = 最长反链。
结论1. $最长反链 = \max\limits_{len}( 长度为 len 的不同子串数量 )$
- 证明考虑末尾为 $len$ 的最长反链，其中比 $len$ 长的子串可以截，长度为 $len$ 的子串可以移动，最后能调整成一个全为 $len$ 的反链。对每个反链都这么搞，对应的是上面的取 $max$ 操作。
结论2. $最长反链 \geq k$ 当且仅当长度为 $n - k + 1$ 的串两两不同。
- 充分性显然。
- 必要性：反证，假设存在两个长度为 $n - k + 1$ 的串相同。考虑长度为 $len$ 的不同子串数量，首先 $len \leq n - k + 1$，其次「长度为 $len$ 的不同子串数量」$\leq n - len + 1 - (n - k + 1 - len + 1) = k - 1$（一个小放缩？），即 $max < k$，矛盾。
我们要求的是最长反链，即 $k_{max}$。$(n - k + 1)_{min} = \max\limits_{1 \leq i < j \leq |S|}( lcp(S[i, ], S[j, ]) ) + 1$，那么 $k_{max} = |S| - \max\limits_{1 \leq i < j \leq |S|}( lcp(S[i, ], S[j, ]) )$，用 SAM 或 SA 即可计算单组询问，$O(nQ)$。
要优化就只有离线或者 LCT 了。我选择离线 _QAQ_
后缀树上启发式合并 endpos 集合，每次合并两个子树的时候把合法对提取出来，最后来个二维数点。提取合法对是 hhz 讲过的套路，由于任意不同子树的对在合并时的贡献都是合并点的 $len$，我们只要挨最近的对，每次是 $O(size_{min})$ 对，总共就是 $O(nlogn)$ 对。
坑点：4 1 caca 1 3 这样的数据告诉你要考虑「第二个串截一半」的情况。
不需要考虑「第一个串截一半」的情况，因为那样意味着更短的 lcp，归其他对管。
具体实现可以搞个备选堆，当前弹掉了就从备选堆里选一个补上。
想补 LCT 做法
金坷垃
咕了，题解看一半看不下去了 /哭
直接做肯定没法做，考虑贡献拆分：$ans_k = \int Pr[第 k 小的数 \geq x] dx$
设 $Pr[第 k 小的数 \geq x]$ 为 $F_k(x)$。
枚举 $k - 1$ 个比第 $k$ 小数小的。
$f_k(x) = \sum\limits_{|s| = k - 1} \prod\limits_{j \in s} Pr[val_j < x] \prod\limits_{j \notin s} (1 - Pr[val_j < x])$
$Pr[val_j < x] = \frac{x - val_j}{m}$ 是分段函数，因此 $F_k(x)$ 是分段多项式
设 $g_k(x) = \sum\limits_{|s| = k - 1} \prod\limits_{j \in s} Pr[val_j < x]$
考虑实际意义：$f_k$ 是恰好 $k$ 个，$g_k$ 是只管 $k$ 个，$g_k = \sum_i \binom{k}{i} f_i$，求出 $g$ 再二项式反演即可得到 $f$
设 $G$ 为 $g$ 的生成函数
$UR$ $21$
挑战最大团
题意：快速统计每个大小的完全子图数量。优美图有性质：不存在一个大小为 $4$ 的点集的生成子图是链。
这种全求出来的题考虑生成函数，OGF。
这个优美图有性质：原图和补图的连通性相反。
- 原图不连通：答案 OGF 为各个连通块 OGF 相加。
- 原图连通：补图不连通，答案 OGF 为补图每个连通块在原图中的 OGF 相乘。
难点在于划分连通块时决定走原图还是补图。原图是个稠密图，共 $n^2$ 条边，直接做最坏复杂度 $O(n^3)$。
定义图的直径为两两之间距离的最大值，距离是最短长度。显然优美图的直径仅为 $2$，也就是说 BFS 两层即可！
如果选一个度数为 $d$ 的点开始 BFS，第一层每个节点需要 $n$ 的代价扩展到第二层，所以这部分是 $O(dn)$
从原图和补图各选度数最小的为起点，同时开始扩展，$O(min(d_1, d_2)n)$ 即可确定哪个不连通。
来分析这个复杂度为什么正确。
设 $min(d_1, d_2) = S$，$n - S = T$，显然 $S \leq T$
被分出来的那个连通块大小为 $S + 1$（这也是这个划分策略基于的性质），因此 $min(d_1, d_2)n = O(Sn) = O(S^2 + ST) = O(ST)$，也就是说划分出大小为 $S$ 和 $T$ 的两个连通块的代价为 $O(ST)$。
一切都很明朗了，这就和树上背包合并 $O(n^2)$ 一个道理。